#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
#include <string.h>

int cmp(const void* a,const void* b)
{
	const short int* ca = (const short int*) a;
	const short int* cb = (const short int*) b;
	return -(*(ca)-*(cb));
}

void insertion_sort (void* base, size_t num, size_t size,
			int (*compar)(const void*,const void*))
{
	int i;
	void *temp = malloc(size);
	for(i=0;i<num;i++)
	{
		int j=i;
		while(j>0&&cmp(base+size*(j-1),base+size*j)>0)
		{
			//Swap
			memcpy(temp,base+size*(j-1),size);
			memcpy(base+size*(j-1),base+size*(j),size);
			memcpy(base+size*j,temp,size);
			j--;
		}
	}
	free(temp);
}

void print_array(short int* a, int n)
{
	int i;
	for (i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}

int main(int argc, char **argv) 
{ 
	int n=0;
	int i;
	short int *t=NULL;
	
	if(argc==1)
	{
		//Reading data from stdin
		if(!(t=malloc(sizeof(short int))))
			exit(-1);
		while (scanf("%hd", &(t[n]))==1)
		{
			n++;
			if(!(t=realloc(t,sizeof(short int)*(n+1))))
				exit(-1);
		}
		if(!(t=realloc(t,sizeof(short int)*(n))))
			exit(-1);
	}
	else
	{
		if(strcmp(argv[1],"--help")==0||strcmp(argv[1],"-h")==0)
		{
			printf("Sorting algorithm (inserction sort). \n\
USAGE: %s options\n\
       %s list_of_integers\n\
    Options:\n\
       --help|-h       This help\n\
       --rand|-r N     Random array of N numbers\n\
    Numbers not specified are awaited in stdin\n\
", argv[0], argv[0]);
			return 0;
		}
		else if(strcmp(argv[1],"--rand")==0||strcmp(argv[1],"-r")==0)
		{
			//Randomly generate array
			if(argc==2)
				scanf("%d", &n);
			else
				n=atoi(argv[2]);
			assert(n>0);
			if(!(t=malloc(sizeof(short int)*n)))
				exit(-1);
			srand(time(NULL)); 
			for (i = 0; i < n; i++)
				t[i] = rand()%100;
		}
		else
		{
			//Read array from argv
			for(n=1;n<argc;n++)
			{
				if(!(t=realloc(t,sizeof(short int)*(n))))
					exit(-1);
				t[n-1]=(short int)atoi(argv[n]);
			}
			n--;
		}
	}
	
	printf("Array:\n");
	print_array(t,n);

	insertion_sort(t,n,sizeof(t[0]),&cmp);

	printf("Sorted array:\n");
	print_array(t,n);
	
	free(t);
	return 0;
}
